\ifx\wholebook\relax \else
% ------------------------

\documentclass{article}
%------------------- Other types of document example ------------------------
%
%\documentclass[twocolumn]{IEEEtran-new}
%\documentclass[12pt,twoside,draft]{IEEEtran}
%\documentstyle[9pt,twocolumn,technote,twoside]{IEEEtran}
%
%-----------------------------------------------------------------------------
%\input{../../../common.tex}
\input{../../../common-en.tex}

\setcounter{page}{1}

\begin{document}

\fi
%--------------------------

% ================================================================
%                 COVER PAGE
% ================================================================

\title{Lists}

\author{Larry~LIU~Xinyu
\thanks{{\bfseries Larry LIU Xinyu } \newline
  Email: liuxinyu95@gmail.com \newline}
  }

\markboth{Sequences}{Elementary Algorithms}

\maketitle

\ifx\wholebook\relax
\chapter{Lists}
\numberwithin{Exercise}{chapter}
\fi

% ================================================================
%                 Introduction
% ================================================================
\section{Introduction}
\label{introduction}

Introduction to C++ template programming as purely functional environment...


\section{List Definition}
\index{List!Definition}

As we mentioned in previous appendix.
More interesting, as far as in an environment support recursion, we can define List. The following
example define a list of integers in C++ compile time.

\lstset{language=C++}
\begin{lstlisting}
struct Empty;

template<int x, typename T> struct List {
  static const int first = x;
  typedef T rest;
};
\end{lstlisting}

These line constructs a list of $\{1, 2, 3, 4, 5\}$ in compile time.

\begin{lstlisting}
typedef List<1, List<2, List<3, List<4 List<5, Empty> > > > > A;
\end{lstlisting}

\section{Basic list manipulation}

\subsection{Construction}

cons in C++ tp

\subsection{Empty testing and length calculating}

Definition...

With empty testing defined, it's possible to calculate length for a list.

The length calculation can also be implemented in C++ template meta programming in purely recursive
manner.

\lstset{language=C++}
\begin{lstlisting}
template<typename L> struct Length {
  static const int value = 1 + Length<typename L::rest>::value;
};

template<> struct Length<Empty> {
  static const int value = 0;
};
\end{lstlisting}

The edge case is written behind the recursive one, that the length value of empty list is 0.
In recursive case, \verb|List::rest| accesses the sub-list of \verb|L|, and \verb|Length<L::rest>::value|
will be recursively calulcated by the C++ compiler. Note that the \verb|typename| keywords should
be inserted before \verb|L::res| to indicate it is a type. After that we add it by 1 as the final
value of the length.

The \verb|Length| calculator can be used as below.

\begin{lstlisting}
cout<<Length<A>::value;
\end{lstlisting}

Where list type \verb|A| is defined in previous section.

How to testing if two lists are identical is left as exercise to the reader.

\subsection{indexing}

For interesting purpose, here are the C++ template meta programming indexing algorithm.

\lstset{language=C++}
\begin{lstlisting}
template<typename L, int i> struct GetAt {
  static const int value = GetAt<typename L::rest, i-1>::value;
};

template<typename L> struct GetAt<L, 0> {
  static const int value = L::first;
};
\end{lstlisting}

The indexing algorithm takes time proportion to the value of index, which is bound to $O(N)$
linear time.

\subsection{Access the last element}

The $last()$ and $init()$ algorithms can also be implemented in C++ template meta programming.

\lstset{language=C++}
\begin{lstlisting}
template<typename L> struct Last {
  static const int value = Last<typename L::rest>::value;
};

template<int x> struct Last<List<x, Empty> > {
  static const int value = x;
};

template<typename L> struct Init {
  typedef List<L::first, typename Init<typename L::rest>::result> result;
};

template<int x> struct Init<List<x, Empty> > {
  typedef Empty result;
};
\end{lstlisting}

Note that the edge case is about the singleton list, which can be specified as \verb|List<x, Empty>|.

\subsection{Reverse indexing}
It's possible to implement the same algorithm in C++ template meta programing as well.
Since $getAtR()$ just wraps most of the work in $examine$, we can define an inner
class template to simulate this fact.

\lstset{language=C++}
\begin{lstlisting}
template<typename L, int i> struct GetAtR {
  template<typename A, typename B> struct Get {
    static const int value = Get<typename A::rest, typename B::rest>::value;
  };

  template<typename A, int x> struct Get<A, List<x, Empty> > {
    static const int value = A::first;
  };

  static const int value = Get<L, typename Drop<i, L>::result>::value;
};
\end{lstlisting}

Where class template \verb|Drop<n, L>| is defined by recursively accessing the rest sub-list $n$ times.

\begin{lstlisting}
template<int n, typename L> struct Drop {
  typedef typename Drop<n-1, typename L::rest>::result result;
};

template<typename L> struct Drop<0, L> {
  typedef L result;
};
\end{lstlisting}

\subsection{Mutating}

\subsubsection{Appending}
For purely interesting purpose, the C++ template meta programming example is given for appending algorithm
as well.

\begin{lstlisting}
template<typename L, int x> struct Append {
  typedef List<L::first, typename Append<typename L::rest, x>::result> result;
};

template<int x> struct Append<Empty, x> {
  typedef List<x, Empty> result;
};
\end{lstlisting}

The edge case is written behind the recursive case as same. That appending an element x to empty list
results a singleton; otherwise, the element is firstly appended to the rest of the list, and we
construct the first element with this recusive appending result to get the final list.

\subsubsection{Mutate element at given position}


\subsubsection{insertion}

include insertion sort

\subsection{deletion}

\subsection{concatenate}

\subsection{sum and product}

\subsection{maximum and minimum}

\begin{Exercise}
\begin{itemize}
\item Given two lists $L_1$ and $L_2$, design a algorithm $eq(L_1, L_2)$ to test if they are equal to each other.
Here equality means the lengths are same, and at the same time, every elements in both list are identical.
\item How to Handle the out-of-bound error case when randomly access the element in a list in C++ template programming?
\item Write a program to print a list.
\end{itemize}
\end{Exercise}

\section{Transformation}

\subsection{mapping and for-each}

\subsection{reverse}

\section{Extract sub-lists}

\section{take and drop}

\section{split at and breaking and grouping}

\section{Folding}

\subsection{folding from left}

\subsection{folding from right}

\subsection{folding in practice}

\subsubsection{concatenate a list of list}

\section{Searching and matching}

\subsection{Existence testing}

\subsection{Looking up}

\subsection{finding and filtering}



\subsection{Matching}

prefix, postfix, and infix

\section{zipping and unzipping}

% ================================================================
%                 Short summary
% ================================================================
\section{Notes and short summary}
...

% ================================================================
%                 Appendix
% ================================================================

\begin{thebibliography}{99}

\bibitem{moderncxx}
Andrei Alexandrescu. ``Modern C++ design: Generic Programming and Design Patterns Applied''. Addison Wesley February 01, 2001, ISBN 0-201-70431-5

\bibitem{mittype}
Benjamin C. Pierce. ``Types and Programming Languages''. The MIT Press, 2002. ISBN:0262162091

\bibitem{SICP}
Harold Abelson, Gerald Jay Sussman, Julie Sussman. ``Structure and Interpretation of Computer Programs, 2nd Edition''. MIT Press, 1996, ISBN 0-262-51087-1

\bibitem{okasaki-book}
Chris Okasaki. ``Purely Functional Data Structures''. Cambridge university press, (July 1, 1999), ISBN-13: 978-0521663502

\bibitem{learn-haskell}
Miran Lipovaca. ``Learn You a Haskell for Great Good! A Beginner's Guide''. No Starch Press; 1 edition April 2011, 400 pp. ISBN: 978-1-59327-283-8

\end{thebibliography}

\ifx\wholebook\relax \else
\end{document}
\fi

% LocalWords:  typedef struct typename
